

class vex{
    constructor(value){
        this.data = value;
        this.firstEdge = null;
        this.in = 0;   //用于存放顶点的入度
    }

}

class adjvex{
    constructor(node,weight){
        this.node = node;
        this.weight = weight;
        this.next = null;
    }
}

class Graph{
    constructor(v,vr){
        this.v=v;
        this.vr=vr;
        let len = v.length;
        let vexs = new Array(len);
        let v1=0,v2=0;
        let newvex = null;
        for (let i=0;i<len;i++){
            vexs[i] = new vex(v[i]);
        }
        for (let arc of vr){
            v1 = v.indexOf(arc[0]);
            v2 = v.indexOf(arc[1]);

            newvex = new adjvex(v2,arc[2]);
            newvex.next = vexs[v1].firstEdge;
            vexs[v1].firstEdge = newvex;
            vexs[v2].in++;
        }
        this.adjList = vexs;
        this.stack=[]; //执行执行顺序
    }

    topoSort(){
        let stack = [];    //辅助栈
        let resStack=[];
        for (let i=0;i<this.adjList.length;i++){   //寻找入度为0的顶点推入栈
            if (this.adjList[i].in === 0){
                stack.push(i);
            }
        }

        let currentVex = null;
        let prevCurrentVex=null;
        let count = 0;         //用于计数已经输出的顶点
        while(stack.length > 0){
            currentVex = this.adjList[stack.pop()];
            console.log(currentVex.data);      //输出栈顶顶点
            resStack.push(currentVex.data);
            count++;
            prevCurrentVex=currentVex;
            currentVex = currentVex.firstEdge;
            while(currentVex){        //删除当前顶点，遍历其邻接顶点，使它们入度减1
                if ((--this.adjList[currentVex.node].in) === 0){  //当邻接顶点入度为0时
                    stack.push(currentVex.node);    //将邻接顶点压入栈中
                }
                currentVex = currentVex.next;
            }
        }
        this.stack=resStack;
        this.errNode='';
        this.errState=true;
        if (count < this.adjList.length){   //若输出的顶点数少于图中顶点数，则存在环
            console.log("存在环路");
            this.errNode=this. prev(prevCurrentVex)
            this.errState=false;
            return false;
        }else{
            this.errState=true;
            return true;
        }
    }

    /**
     * 获取 下一个 边
     * @param prevCurrentVex
     * @returns {null}
     */
    prev(prevCurrentVex){
        let xx=null;
        for(let i=0;i<this.vr.length;i++){
            if(prevCurrentVex==this.vr[i][0]){
                xx=this.vr[i][1];
            }
        }
        return xx;

    }

    run(){
    debugger

    }

}
//
// let g = [
//     [ 'a','b','c','d'   ]
//     ,
//     [['a','b',1],['b','c',1],['d','b',1]   ]
//
// ]
// debugger
// let a=new Graph(g[0],g[1])
// console.log(a);
// console.log('---------------');
//
// let b = a.topoSort();
// debugger
// console.log(b)
// console.log(a)
export default Graph
